As prior arts concerning pattern processing methods for computer-aided design or computer graphics, there have been proposed various methods concerning definition, processing, editing, display, etc., of two- or three-dimensional regions. In regard to the method of processing three-dimensional solids, which is the subject matter of the present invention, the following three typical techniques are known:
(1) Boundary Representation (hereinafter abbreviated as "B-rep method") PA1 (2) Constructive Solid Geometry (hereinafter abbreviated as "CSG method") PA1 (3) Octree Method PA1 (I) It must be possible to define, process, edit and display regions varying in configuration over a wide range and also output characteristic values of each region. PA1 (II) It must be possible to ensure processing results which are effective to any possible combination of data. In other words, the pattern processing method must be solid. PA1 (III) Regarding the above (II), it must be possible to ensure processing precision required for each particular purpose. PA1 (IV) The pattern processing method and the format of configurational data concerned therewith must be simple, and the amount of data must be small. PA1 (1) means for providing a procedure (hereinafter referred to as "relative expression procedure") for generating relative positional data of any desired point P in the space with respect to the region in a fixed format by the use of a series of data determining the region, thereby identifying the region with the procedure, and thus unitarily determining the region; PA1 (2) means for generating a relative expression procedure for a new region from the relative expression procedure(s) of one or more regions given the procedures (hereinafter referred to as "relatively expressed region(s)"), the relative expression procedure for the new region being obtained by configurationally processing and editing the one or more relatively expressed regions, thereby relatively expressing the new region; and PA1 (3) means for expressing configurational characteristics of each relatively expressed region itself by the use of the relative expression procedure of the region.
This method was proposed by Braid. According to the method, the configuration of each three-dimensional region is structurally expressed by a combination of topological and geometrical data concerning surfaces, edges and vertexes, thus enabling a set operation between regions on the basis of these data. As a literature making mention of the B-rep method, an article entered in Computer Aided Design of Mechanical Components with Volume Building Bricks, Proc. 2nd Int. IFIP/IFAC Conference, Budapest, PP174, 1973 is known.
This method was proposed by Prof. Norio Okino. The method is based on the assumption that a desired region is constructively formed from basic regions, for example, a cube, sphere, circular cylinder, etc. by performing a set operation, and a desired region is expressed by showing the process of a set operation with a tree structure. This method needs special techniques for calculating characteristic quantities of the resulting region and displaying the configuration of the region. As a literature concerning the CSG method, an article entered in TIPS-1; Technical Information Processing System for Computer Aided Design, Drawing and Manufacturing, Proc. 2nd Int. IFIP/IFAC, P-RORAMAT Conference, Budapest, PP141, 1973 is known.
This method was proposed by Hunter. In this method, the principle of the quadtree method that hardles two-dimensional regions is applied to three-dimensional ones. According to the quadtree method and the octree method, regions are expressed in the form of quadtrees and octrees, respectively. As literature concerning the quadtree method, there the specification of U.S. Pat. No. 3,062,702 (Aug. 3, 1981) to Warnock. As a literature concerning the octree method, there is a thesis submitted to the Electronics & Computer Science Department of Princeton University, entitled "Effective Computer Utilization and Data Structure For Graphics".
The following four points are important to a pattern processing method for computer-aided design or computer graphics, although the weight somewhat differs depending upon each particular purpose:
The B-rep method that is one of the above-described prior arts is satisfactory in regard to the above-described point (I) but incomplete in regard to the above-described point (II) and has many problems in regard to the other points (III) and (IV). The CSG method has a problem in regard to the above-described (I) since there is a restriction on the number of kinds of configuration of regions which can be handled. The octree method is, in principle, superior to the other methods in regard to all the points. However, in regard to the above-described point (III ), for example, if it is intended to prepare information concerning machining a mechanical product which needs to ensure practical tolerances, the amount of data required therefor is so large that it exceeds the limit of the range within which data can be handled in practical use, thus causing a problem in regard to the above-described point (IV).
As has been described above, any of the prior art methods has the problems that it cannot be applied to a wide range of applications and it is insufficient to function as a pattern processing method which is solid, clear and simple.
It is an object of the present invention to provide a pattern processing method which has solved the above-described problems of the prior arts and enables simplication of the processing system and a reduction in the amount of data necessary to handle, thus meeting all the above -described requirements (1) to (4).